package sort.bucket;

import org.junit.Test;

import java.util.Arrays;

/**
 * 基数排序
 * 基数r 是关键字每一位的取值种数
 */
public class RadixSort {
    public int[] radixSort(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }

        //存储排序后的数组
        int[] ans = new int[nums.length];

        int max = nums[0];

        //计数的数组
        int[] count = new int[10];  // 0 ~ 9，关键字的每个部位都可以得到十种不同的取值

        //找到最大值
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
        }

        //计算出最大位数N
        int N = 0;
        while (max > 0) {
            N++;
            max /= 10;
        }

        //总共需要进行N趟分配、收集
        for (int i = 0; i < N; i++) {
            int division = (int) Math.pow(10, i);

            //分配 将同一位上数值相同 对应的槽位+1
            for (int j = 0; j < nums.length; j++) {
                int num = nums[j] / division % 10; //取模，求出个、十、百...位对应的数值
                count[num]++;
            }

            for (int k = 1; k < count.length; k++) {
                count[k] = count[k - 1] + count[k];
            }

            //整理，将槽位上的元素排到ans数组上
            for (int j = nums.length - 1; j >= 0; j--) {
                int num = nums[j] / division % 10;  // num 表示该nums[j] 某一位上的数值
                int index = count[num] - 1;         // 对应在ans数组的索引
                ans[index] = nums[j];               // 映射到ans数组上
                count[num]--;                       // count数组
            }

            //将ans数组的内容复制到nums数组，即完成一次整理
            System.arraycopy(ans, 0, nums, 0, nums.length);

            //清理count数组
            Arrays.fill(count, 0);
        }
        return ans;
    }

    @Test
    public void test() {
        int[] nums = {5, 2, 7, 4, 1, 3, 8, 9};
        nums = radixSort(nums);

        for (int num : nums) {
            System.out.print(num+" ");
        }
    }
}